#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int minCut(string s) {
    int n = s.size();

    vector<vector<bool>> isPal(n, vector<bool>(n));

    for (int i = n - 1; i >= 0; --i)
        for (int j = i; j < n; ++j)
            if (s[i] == s[j])
                isPal[i][j] = i + 1 >= j ? true : isPal[i + 1][j - 1];

    vector<int> dp(n + 1, INT_MAX);
    for (int i = 0 ; i < n; ++i)
    {
        if (isPal[0][i])
            dp[i] = 0;
        else
        {
            for (int j = 1; j <= i; ++j)
                if (isPal[j][i])
                    dp[i] = min(dp[i], dp[j - 1] + 1);
        }
    }

    return dp[n - 1];
}

int main()
{
    minCut("aab");
    return 0;
}